Vào thập niên 1450, Shari'ful Hashem Syed Abu Bakr, một người Ả Rập sinh tại Johor, đã từ Malacca tới Sulu. Vào năm 1457, ông lập ra nước Sulu và, sau đó, tự đổi tên thành Paduka Maulana Mahasari Sharif Sultan Hashem Abu Bakr. Trước thời điềm này quãng vài chục năm, Nhà nước Hồi giáo Brunei cũng đã được thành lập.

Vào năm 1703 (có tài liệu ghi là 1658), phần đất Bắc Borneo (nay là bang Sabah của Malaysia) trở thành lãnh thổ của Sulu. Vua Brunei sau khi nhận được sự trợ giúp của Sulu để chống lại bạo loạn trong nước và cướp biển, đã tặng cho vua Sulu phần đất này. Tuy vậy, trong cùng năm đó, vua Sulu đem tặng đảo Palawan cho vua Quadarat (1619-1671) của Nhà nước Hồi giáo Maguindanao như một món quà dẫn cưới sau khi ông vua này kết hôn với con gái của vua Sulu và kết thành liên minh Sulu-Maguindanao. Tuy vậy, chỉ hai năm sau, vào năm 1705, vua Maguindanao là Bayan ul-Anwar Maruhom Batua (1702-1736) đã để mất Palawan vào tay người Tây Ban Nha.